/* 808. 分汤 */
/**
 * @param {number} n
 * @return {number}
 */

/* 
    动态规划
    由于4中分配都是25的倍数 因此我们可以将n初以25
    4中分配操作变成 (4,1) (3,1) (2,2) (1,3) 且每种操作
    的概率均为 0.25

    dp(i,j) 表示汤A和汤B 分别剩下i和j 份时所求的概率值， 即汤A先分配完的 
    概率 + 汤A和汤B同时分配完的概率除以2 状态转移方程为 
    dp(i,j) = 1/4 * (dp(i-4,j)+dp(i-3,j-1)+dp(i-2,j-2)+dp(i-1,j-3))

    当满足 i > 0 ，j = 0 此时 再无法分配，而汤A还未分配完成，汤A永远无法完成分配 此时 dp(i,j) = 0

    当满足 i = 0，j = 0 此时，汤A和汤B同时分配完的概率为1汤A先分配完的概率为0 因此 dp(i,j) = 1 * 0.5 = 0.5
    
    当满足i = 0, j > 0 ，此时无法再分配，汤A先分配完的概率为1.0 汤B 永远无法完后分配因此dp(i,j) = 1
*/
var soupServings = function (n) {
	n = Math.ceil(n / 25)
	if (n >= 179) return 1
	const dp = new Array(n + 1).fill(0).map(() => new Array(n + 1).fill(0))
	dp[0][0] = 0.5

	for (let i = 1; i <= n; i++) {
		dp[0][i] = 1
	}

	for (let i = 1; i <= n; i++) {
		for (let j = 1; j <= n; j++) {
			dp[i][j] =
				(dp[Math.max(0, i - 4)][j] +
					dp[Math.max(0, i - 3)][Math.max(0, j - 1)] +
					dp[Math.max(0, i - 2)][Math.max(0, j - 2)] +
					dp[Math.max(0, i - 1)][Math.max(0, j - 3)]) /
				4
		}
	}
	return dp[n][n]
}
// 记忆化搜索
var soupServings = function (n) {
	n = Math.ceil(n / 25)
	if (n >= 179) return 1
	const memo = new Array(n + 1).fill(0).map(() => new Array(n + 1).fill(0))
	const dfs = (a, b) => {
		if (a <= 0 && b <= 0) {
			return 0.5
		} else if (a <= 0) {
			return 1
		} else if (b <= 0) {
			return 0
		}
		if (memo[a][b] === 0) {
			memo[a][b] =
				(dfs(a - 4, b) +
					dfs(a - 3, b - 1) +
					dfs(a - 2, b - 2) +
					dfs(a - 1, b - 3)) /
				4
		}
		return memo[a][b]
	}
	return dfs(n, n)
}
